// #include <iostream>
// #include <assert.h>
// #include <stdlib.h>
// #include <algorithm>
// using std::cin;
// using std::cout;
// using std::endl;

// // //namespace sl
// // //{
// // //  //节点类
// // //  template<class T>
// // //  struct list_node
// // //  {
// // //    list_node(const T& val = T())
// // //      :_prev(nullptr)
// // //       ,_next(nullptr)
// // //       ,_data(val)
// // //    {}
// // //
// // //    list_node<T>* _prev;
// // //    list_node<T>* _next;
// // //    T _data;
// // //  };
// // //
// // //  //迭代器
// // //  template<class T>
// // //  struct __list_iterator
// // //  {
// // //    typedef list_node<T> Node;
// // //    Node* _node;
// // //
// // //    //构造
// // //    __list_iterator(Node* node)
// // //      :_node(node)
// // //    {}
// // //
// // //    T& operator*()
// // //    {
// // //      return _node->_data;
// // //    }
// // //
// // //    __list_iterator<T>& operator++()
// // //    {
// // //      _node = _node->next;
// // //      return *this;
// // //    }
// // //
// // //    bool operator!=(const __list_iterator<T>& it)
// // //    {
// // //      return _node != it._node;
// // //    }
// // //
// // //    T* operator->()
// // //    {
// // //      return &(operator*());
// // //    }
// // //
// // //
// // //
// // //    //List类
// // //    template<class T>
// // //    class List
// // //    {
// // //      typedef list_node<T> Node;
// // //    public:
// // //      typedef __list_iterator<T> iterator;
// // //
// // //      List()
// // //      {
// // //        _head = new Node();
// // //        _head->_next = _head;
// // //        _head->_prev = _head;
// // //      }
// // //    private:
// // //      Node* _head;
// // //    };
// // //
// // //  };
// // //}

// // //namespace sl
// // //{
// // //  //节点类
// // //  template<class T>
// // //  struct list_node
// // //  {
// // //    list_node(const T& val = T())
// // //      :_prev(nullptr)
// // //      ,_next(nullptr)
// // //      ,_data(val)
// // //    {}
// // //
// // //    list_node<T>* _prev;
// // //    list_node<T>* _next;
// // //    T _data;
// // //  };
// // //
// // //  //迭代器类
// // //  template<class T>
// // //  struct __list_iterator
// // //  {
// // //    typedef list_node<T> Node;
// // //    Node* _node;
// // //
// // //    //构造
// // //    __list_iterator(Node* node)
// // //      :_node(node)
// // //    {}
// // //
// // //    T& operator*()
// // //    {
// // //      return _node->_data;
// // //    }
// // //
// // //    __list_iterator<T>& operator++()
// // //    {
// // //      _node = _node->next;
// // //      return *this;
// // //    }
// // //
// // //    bool operator!=(const __list_iterator<T>& lt)
// // //    {
// // //      return _node != lt._node;
// // //    }
// // //
// // //    T* operator->()
// // //    {
// // //      return &(operator*());
// // //    }
// // //  };
// // //
// // //  //List类
// // //  template<class T>
// // //  class List
// // //  {
// // //  public:
// // //    typedef list_node<T> Node;
// // //    typedef __list_iterator<T> iterator;
// // //
// // //    List()
// // //    {
// // //      _head = new Node();
// // //      _head->_prev = _head;
// // //      _head->_next = _head;
// // //    }
// // //
// // //    void push_back(const T& x)
// // //    {
// // //      Node* newnode = new Node(x);
// // //      Node* tail = _head->_prev;
// // //      tail->_next = newnode;
// // //      newnode->_prev = tail;
// // //      newnode->_next = _head;
// // //      _head->_prev = newnode;
// // //    }
// // //
// // //    iterator begin()
// // //    {
// // //      return iterator(_head->_next);
// // //    }
// // //
// // //    iterator end()
// // //    {
// // //      return iterator(_head);
// // //    }
// // //
// // //  private:
// // //    Node*  _head;
// // //  };
// // //}

// // //namespace sl
// // //{
// // //  //节点类
// // //  template<class T>
// // //  struct list_node
// // //  {
// // //    //构造
// // //    list_node(const T& val = T())
// // //      :_prev(nullptr)
// // //      ,_next(nullptr)
// // //      ,_data(val)
// // //    {}
// // //
// // //    list_node<T>* _prev;
// // //    list_node<T>* _next;
// // //    T _data;
// // //  };
// // //
// // //  ////迭代器类——实现成像指针一样的东西
// // //  //struct __List_iterator
// // //  //{
// // //  //  typedef list_node<T> Node;
// // //
// // //  //  __list_iterator(Node* node)
// // //  //    :_node(node)
// // //  //  {}
// // //  //  Node* _node;
// // //
// // //  //  T& operator*()
// // //  //  {
// // //  //    return _node->_data;
// // //  //  }
// // //
// // //  //  __list_iterator<T>& operator++()
// // //  //  {
// // //  //    _node = _node->_next;
// // //  //    return *this;
// // //  //  }
// // //
// // //  //  bool operator!=(const __list_iterator& lt)
// // //  //  {
// // //  //    return _node != lt._node;
// // //  //  }
// // //  //};
// // //
// // //
// // //  //迭代器类——实现成像指针一样的功能
// // //  template<class T, class Ref, class Ptr>
// // //  struct __list_iterator
// // //  {
// // //    typedef list_node<T> Node;
// // //    typedef __list_iterator<T, Ref, Ptr> Self;
// // //    Node* _node;
// // //
// // //    //构造
// // //    __list_iterator(Node* node)
// // //      :_node(node)
// // //    {}
// // //
// // //    Ref operator*()
// // //    {
// // //      return _node->_data;
// // //    }
// // //
// // //    Ptr operator->()
// // //    {
// // //      return &(operator*());
// // //    }
// // //
// // //    bool operator!=(const Self& lt)
// // //    {
// // //      return _node != lt._node;
// // //    }
// // //
// // //    bool operator==(const Self& lt)
// // //    {
// // //      return _node == lt._node;
// // //    }
// // //
// // //    //前置
// // //    Self& operator++()
// // //    {
// // //      _node = _node->_next;
// // //      return *this;
// // //    }
// // //
// // //    //后置
// // //    Self operator++(int)
// // //    {
// // //      Self tmp(*this);
// // //      _node = _node->_next;
// // //      return tmp;
// // //    }
// // //
// // //    //前置
// // //    Self& operator--()
// // //    {
// // //      _node = _node->prev;
// // //      return *this;
// // //    }
// // //
// // //    //后置
// // //    Self operator--(int)
// // //    {
// // //      Self tmp(*this);
// // //      _node = _node->_prev;
// // //      return tmp;
// // //    }
// // //  };
// // //
// // //
// // //  //List类
// // //  template<class T>
// // //  class List
// // //  {
// // //  public:
// // //    typedef __list_iterator<T, T&, T*> iterator;
// // //    typedef __list_iterator<T, const T&, const T*> const_iterator;
// // //    typedef list_node<T> Node;
// // //
// // //    List()
// // //    {
// // //      _head = new Node();
// // //      _head->_prev = _head;
// // //      _head->_next = _head;
// // //    }
// // //
// // //    //lt2(lt1);
// // //    List(const List<T>& lt)
// // //    {
// // //      Head_Init();
// // //
// // //      for(auto& e : lt)
// // //      {
// // //        push_back(e);
// // //      }
// // //    }
// // //
// // //    template<class InputIterator>
// // //    List(InputIterator first, InputIterator last)
// // //    {
// // //      Head_Init();
// // //
// // //      whiel(first != last)
// // //      {
// // //        push_back(*first);
// // //        first++;
// // //      }
// // //    }
// // //
// // //    void Head_Init()
// // //    {
// // //      _head = new Node();
// // //      _head->_prev = _head;
// // //      _head->_next = _head;
// // //    }
// // //
// // //
// // //    void swap(List<T>& lt)
// // //    {
// // //      std::swap(_head, lt._head);
// // //    }
// // //
// // //    //lt2(lt1);——现代写法
// // //    List(const List<T>& lt)
// // //    {
// // //      Head_Init();
// // //
// // //      List<T> tmp(lt.begin(), lt.end());
// // //      swap(tmp);
// // //    }
// // //
// // //    //lt1 = lt2;
// // //    List<T>& operator=(List<T> lt)
// // //    {
// // //      swap(lt);
// // //      return *this;
// // //    }
// // //
// // //    ~List()
// // //    {
// // //      clear();
// // //
// // //      delete _head;
// // //      _head = nullptr;
// // //    }
// // //
// // //    void clear()
// // //    {
// // //      iterator it = begin();
// // //      while(it != end())
// // //      {
// // //        it = it.erase(it);
// // //      }
// // //    }
// // //
// // //    void push_back(const T& x)
// // //    {
// // //      //Node* newnode = new Node(x);
// // //      //Node* tail = _head->_prev;
// // //
// // //      //tail->_next = newnode;
// // //      //newnode->_prev = tail;
// // //      //_head->_prev = newnode;
// // //      //newnode->_next = _head;
// // //
// // //      insert(end(), x);
// // //    }
// // //
// // //    void push_front(const T& x)
// // //    {
// // //      insert(begin(), x);
// // //    }
// // //
// // //    void pop_back()
// // //    {
// // //      erase(--end());
// // //    }
// // //
// // //    void pop_front()
// // //    {
// // //      erase(begin());
// // //    }
// // //
// // //    //在pos位置之前插入
// // //    iterator insert(iterator pos, const T& x)
// // //    {
// // //      Node* newnode = new Node(x);
// // //      Node* cur = pos._node;
// // //      Node* prev = cur->_prev;
// // //
// // //      //prev newnode cur
// // //      prev->_next = newnode;
// // //      newnode->_prev = prev;
// // //      newnode->_next = cur;
// // //      cur->_prev = newnode;
// // //
// // //      return iterator(newnode);
// // //
// // //    }
// // //
// // //    //删除pos位置的值
// // //    iterator erase(iterator pos)
// // //    {
// // //      assert(pos < end());
// // //
// // //      Node* cur = pos._node;
// // //      Node* next = cur->_next;
// // //      Node* prev = cur->_prev;
// // //
// // //      prev->_next = next;
// // //      next->_prev = prev;
// // //      delete cur;
// // //      cur = nullptr;
// // //
// // //      return iterator(next);
// // //    }
// // //
// // //
// // //    iterator begin()
// // //    {
// // //      return iterator(_head->_next);
// // //    }
// // //
// // //    iterator end()
// // //    {
// // //      return iterator(_head);
// // //    }
// // //
// // //    const_iterator begin()const
// // //    {
// // //      return iterator(_head->_next);
// // //    }
// // //
// // //    const_iterator end()const
// // //    {
// // //      return iterator(_head);
// // //    }
// // //
// // //
// // //
// // //
// // //  private:
// // //    Node* _head;
// // //  };
// // //}

// // // namespace sl
// // // {
// // //   //节点类
// // //   template<class T>
// // //   struct list_node
// // //   {
// // //     list_node(const T& val = T())
// // //       :_prev(nullptr)
// // //       ,_next(nullptr)
// // //       ,_data(val)
// // //     {}

// // //     list_node<T> _prev;
// // //     list_node<T> _next;
// // //     T _data;
// // //   };

// // //   //迭代器类
// // //   template<class T, class Ref, class Ptr>
// // //   struct __list_iterator
// // //   {
// // //     typedef list_node<T> Node;
// // //     typedef __list_iterator<T> Self;

// // //     Node* _node;
// // //     __list_iterator(Node* node)
// // //       :_node(node)
// // //     {}

// // //     T& operator*()
// // //     {
// // //       return _node->_data;
// // //     }

// // //     T* operator&()
// // //     {
// // //       return &(operator*());
// // //     }

// // //     Self& operator++()
// // //     {
// // //       _node = _node->_next;
// // //       return _node;
// // //     }

// // //     Self operator++(int)
// // //     {
// // //       Self tmp(_node);
// // //       _node = _node->_next;
// // //       return tmp;
// // //     }

// // //     Self operator--()
// // //     {

// // //     }
// // //   };
// // // }

// // // namespace sl
// // // {
// // //     //节点类
// // //     template<class T>
// // //     struct list_node
// // //     {
// // //         list_node(const T& x = T())
// // //             :_prev(nullptr)
// // //             ,_next(nullptr)
// // //             ,_data(x)
// // //         {}

// // //         list_node<T>* _prev;
// // //         list_node<T>* _next;
// // //         T _data;
// // //     };

// // //     //迭代器类
// // //     template<class T, class Ref, class Ptr>
// // //     struct __list_iterator
// // //     {
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, Ref, Ptr> Self;

// // //         Node* _node;

// // //         __list_iterator(Node* node)
// // //             :_node(node)
// // //         {}

// // //         Ref operator*()
// // //         {
// // //             return _node->_data;
// // //         }

// // //         Ptr operator->()
// // //         {
// // //             return &(operator*());
// // //         }

// // //         //前置++
// // //         Self& operator++()
// // //         {
// // //             _node = _node->_next;
// // //             return *this;
// // //         }

// // //         //后置++
// // //         Self operator++(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_next;
// // //             return tmp;
// // //         }

// // //         //前置--
// // //         Self& operator--()
// // //         {
// // //             _node = _node->_prev;
// // //             return *this;
// // //         }

// // //         //后置--
// // //         Self operator--(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_prev;
// // //             return tmp;
// // //         }

// // //         bool operator==(const Self& lt)
// // //         {
// // //             return _node == lt._node;
// // //         }

// // //         bool operator!=(const Self& lt)
// // //         {
// // //             return _node != lt._node;
// // //         }
// // //     };

// // //     //List类
// // //     template<class T>
// // //     class List
// // //     {
// // //     public:
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, T&, T*> iterator;
// // //         typedef __list_iterator<T, const T&,const T*> const_iterator;

// // //         List(const T& x = T())
// // //         {
// // //             _head = new Node(x);
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         void Head_Init()
// // //         {
// // //             _head = new Node();
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         //迭代器区间构造
// // //         List(iterator first, iterator last)
// // //         {
// // //             Head_Init();

// // //             iterator it = first;
// // //             while(first != last)
// // //             {
// // //                 push_back(*first);
// // //                 first++;
// // //             }
// // //         }

// // //         void swap(List<T>& lt)
// // //         {
// // //             std::swap(_head, lt._head);
// // //         }

// // //         //现代写法——拷贝构造
// // //         List(const List<T>& lt)
// // //         {
// // //             Head_Init();

// // //             List<T> tmp(lt._head);
// // //             swap(tmp);
// // //         }

// // //         List<T>& operator=(List<T> lt)
// // //         {
// // //             swap(lt);
// // //             return *this;
// // //         }

// // //         iterator begin()
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         iterator end()
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         const_iterator begin()const
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         const_iterator end()const
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         void push_back(const T& x)
// // //         {
// // //             insert(end(), x);
// // //         }

// // //         void push_front(const T& x)
// // //         {
// // //             insert(begin(), x);
// // //         }

// // //         void pop_back()
// // //         {
// // //             erase(--end());
// // //         }

// // //         void pop_front()
// // //         {
// // //             erase(begin());
// // //         }

// // //         //在pos位置前插入一个节点
// // //         iterator insert(iterator pos, const T& x)
// // //         {
// // //             Node* newnode = new Node(x);
// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;

// // //             //prev newnode cur
// // //             newnode->_prev = prev;
// // //             prev->_next = newnode;
// // //             newnode->_next = cur;
// // //             cur->_prev = newnode;

// // //             return iterator(newnode);
// // //         }

// // //         iterator erase(iterator pos)
// // //         {
// // //             assert(pos != end());

// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;
// // //             Node* next = cur->_next;

// // //             //prev cur next
// // //             prev->_next = next;
// // //             next->_prev = prev;
// // //             delete cur;
// // //             cur = nullptr;

// // //             return iterator(next);
// // //         }

// // //         void display()
// // //         {
// // //             iterator it = begin();
// // //             while(it != end())
// // //             {
// // //                 cout << it._node->_data << " ";
// // //                 it++;
// // //             }

// // //             cout << endl;
// // //         }
// // //     private:
// // //         Node* _head;

// // //     };
// // // }

// // // int main()
// // // {
// // //     sl::List<int> l;
// // //     l.push_back(1);
// // //     l.push_back(2);
// // //     l.push_back(3);
// // //     l.push_back(4);
// // //     l.push_back(5);

// // //     l.display();

// // //     l.pop_front();
// // //     l.pop_front();
// // //     l.pop_front();

// // // //     l.display();

// // // //     return 0;
// // // // }

// // // namespace sl
// // // {
// // //     //节点类
// // //     template<class T>
// // //     struct list_node
// // //     {
// // //         list_node(const T& x = T())
// // //             :_prev(nullptr)
// // //             ,_next(nullptr)
// // //             ,_data(x)
// // //         {}

// // //         list_node<T> _prev;
// // //         list_node<T> _next;
// // //         T _data;
// // //     };

// // //     //迭代器类
// // //     template<class T, class Ref, class Ptr>
// // //     struct __list_iterator
// // //     {
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, T&, T*> Self;

// // //         __list_iterator(Node* node)
// // //             :_node(node)
// // //         {}
// // //         Node* _node;

// // //         Ref operator*()
// // //         {
// // //             return _node->_data;
// // //         }

// // //         Ptr operator->()
// // //         {
// // //             return &(operator*());
// // //         }

// // //         //前置++
// // //         Self& operator++()
// // //         {
// // //             _node = _node->_next;
// // //             return *this;
// // //         }

// // //         //后置++
// // //         Self operator++(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_next;
// // //             return tmp;
// // //         }

// // //         //前置--
// // //         Self& operator--()
// // //         {
// // //             _node = _node->_prev;
// // //             return *this;
// // //         }

// // //         //后置--
// // //         Self operator--(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_prev;
// // //             return tmp;
// // //         }

// // //         bool operator==(const Self& lt)
// // //         {
// // //             return _node == lt._node;
// // //         }

// // //         bool operator!=(const Self& lt)
// // //         {
// // //             return _node != lt._node;
// // //         }
// // //     };

// // //     //List类
// // //     template<class T>
// // //     class List
// // //     {
// // //     public:
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, T&, T*> iterator;
// // //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// // //         List()
// // //         {
// // //             _head = new Node();
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         iterator begin()
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         iterator end()
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         const_iterator begin()const
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         const_iterator end()const
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         //在pos位置之前插入
// // //         iterator insert(iterator pos, const T& x)
// // //         {
// // //             Node* newnode = new Node(x);
// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;

// // //             //prev newnode cur
// // //             prev->_next = newnode;
// // //             newnode->_prev = prev;
// // //             newnode->_next = cur;
// // //             cur->_prev = newnode;

// // //             return iterator(newnode);
// // //         }

// // //         iterator erase(iterator pos)
// // //         {
// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;
// // //             Node* next = cur->_next;

// // //             prev->_next = next;
// // //             next->_prev = prev;
// // //             delete cur;
// // //             cur = nullptr;

// // //             return iterator(next);
// // //         }

// // //     private:
// // //         Node* _head;

// // //     };
// // // }

// // // namespace sl
// // // {
// // //     //节点类
// // //     template<class T>
// // //     struct list_node
// // //     {
// // //         list_node(const T& x = T())
// // //             :_prev(nullptr)
// // //             ,_next(nullptr)
// // //             ,_data(x)
// // //         {}

// // //         list_node<T>* _prev;
// // //         list_node<T>* _next;
// // //         T _data;
// // //     };

// // //     //迭代器类
// // //     template<class T, class Ref, class Ptr>
// // //     struct __list_iterator
// // //     {
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, Ref, Ptr> Self;

// // //         Node* _node;

// // //         __list_iterator(Node* node)
// // //             :_node(node)
// // //         {}

// // //         Ref operator*()
// // //         {
// // //             return _node->_data;
// // //         }

// // //         Ptr operator->()
// // //         {
// // //             return &(operator*());
// // //         }

// // //         //前置++
// // //         Self& operator++()
// // //         {
// // //             _node = _node->_next;
// // //             return *this;
// // //         }

// // //         //后置++
// // //         Self operator++(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_next;
// // //             return tmp;
// // //         }

// // //         //前置--
// // //         Self& operator--()
// // //         {
// // //             _node = _node->_prev;
// // //             return *this;
// // //         }

// // //         //后置--
// // //         Self operator--(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_prev;
// // //             return tmp;
// // //         }

// // //         bool operator==(const Self& lt)
// // //         {
// // //             return _node == lt._node;
// // //         }

// // //         bool operator!=(const Self& lt)
// // //         {
// // //             return _node != lt._node;
// // //         }

// // //     };

// // //     //List类
// // //     template<class T>
// // //     class List
// // //     {
// // //     public:
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, T&, T*> iterator;
// // //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// // //         List()
// // //         {
// // //             _head = new Node();
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         //迭代器区间构造
// // //         template<class InputIterator>
// // //         List(InputIterator first, InputIterator last)
// // //         {
// // //             Head_Init();

// // //             while(first != last)
// // //             {
// // //                 push_back(*first);
// // //                 first++;
// // //             }
// // //         }

// // //         void Head_Init()
// // //         {
// // //             _head = new Node();
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         void swap(List<T>& lt)
// // //         {
// // //             std::swap(_head, lt._head);
// // //         }

// // //         //拷贝构造
// // //         List(const List<T>& lt)
// // //         {
// // //             Head_Init();

// // //             List<T> tmp(lt.begin(), lt.end());
// // //             swap(tmp);
// // //         }

// // //         //赋值重载
// // //         List<T>& operator=(List<T> lt)
// // //         {
// // //             swap(lt);
// // //             return *this;
// // //         }

// // //         void clear()
// // //         {
// // //             iterator it = begin();
// // //             while(it != end())
// // //             {
// // //                 it = erase(it);
// // //             }
// // //         }

// // //         ~List()
// // //         {
// // //             clear();
// // //             delete _head;
// // //             _head = nullptr;
// // //         }

// // //         iterator begin()
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         iterator end()
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         const_iterator begin()const
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         const_iterator end()const
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         iterator insert(iterator pos, const T& x)
// // //         {
// // //             Node* newnode = new Node(x);
// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;
// // //             //prev newnode cur
// // //             prev->_next = newnode;
// // //             newnode->_prev = prev;
// // //             newnode->_next = cur;
// // //             cur->_prev = newnode;

// // //             return iterator(newnode);
// // //         }

// // //         iterator erase(iterator pos)
// // //         {
// // //             assert(pos != end());

// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;
// // //             Node* next = cur->_next;

// // //             //prev cur next
// // //             prev->_next = next;
// // //             next->_prev = prev;
// // //             delete cur;
// // //             cur = nullptr;

// // //             return iterator(next);
// // //         }

// // //         void push_back(const T& x)
// // //         {
// // //             insert(end(), x);
// // //         }

// // //         void push_front(const T& x)
// // //         {
// // //             insert(begin(), x);
// // //         }

// // //         void pop_back()
// // //         {
// // //             erase(--end());
// // //         }

// // //         void pop_front()
// // //         {
// // //             erase(begin());
// // //         }

// // //         void Display()
// // //         {
// // //             iterator it = begin();
// // //             while(it != end())
// // //             {
// // //                 cout << it._node->_data << " ";
// // //                 it++;
// // //             }
// // //             cout << endl;
// // //         }
// // //     private:
// // //         Node* _head;
// // //     };
// // // }

// // // // int main()
// // // // {
// // // //     sl::List<int> lt;
// // // //     lt.push_back(1);
// // // //     lt.push_back(2);
// // // //     lt.push_back(3);
// // // //     lt.push_back(4);
// // // //     lt.push_back(5);
// // // //     lt.push_back(6);
// // // //     lt.push_back(7);

// // // //     lt.Display();

// // // //     return 0;
// // // // }

// // // namespace sl
// // // {
// // //     //节点类
// // //     template<class T>
// // //     struct list_node
// // //     {
// // //         list_node(const T& val = T())
// // //             :_prev(nullptr)
// // //             ,_next(nullptr)
// // //             ,_data(val)
// // //         {}

// // //         list_node<T>* _prev;
// // //         list_node<T>* _next;
// // //         T _data;
// // //     };

// // //     //迭代器
// // //     template<class T, class Ref, class Ptr>
// // //     struct __list_iterator
// // //     {
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, Ref, Ptr> Self;

// // //         Node* _node;

// // //         __list_iterator(Node* node)
// // //             :_node(node)
// // //         {}

// // //         Ref operator*()
// // //         {
// // //             return _node->_data;
// // //         }

// // //         Ptr operator->()
// // //         {
// // //             //return &(operator*());
// // //             return &_node->_data;
// // //         }

// // //         bool operator==(const Self& lt)
// // //         {
// // //             return _node == lt._node;
// // //         }

// // //         bool operator!=(const Self& lt)
// // //         {
// // //             return _node != lt._node;
// // //         }

// // //         //前置++
// // //         Self& operator++()
// // //         {
// // //             _node = _node->_next;
// // //             return *this;
// // //         }

// // //         //后置++
// // //         Self operator++(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_next;
// // //             return tmp;
// // //         }

// // //         //前置--
// // //         Self& operator--()
// // //         {
// // //             _node = _node->_prev;
// // //             return *this;
// // //         }

// // //         //后置--
// // //         Self operator--(int)
// // //         {
// // //             Self tmp(*this);
// // //             _node = _node->_prev;
// // //             return tmp;
// // //         }
// // //     };

// // //     //List类
// // //     template<class T>
// // //     class List
// // //     {
// // //     public:
// // //         typedef list_node<T> Node;
// // //         typedef __list_iterator<T, T&, T*> iterator;
// // //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// // //         List()
// // //         {
// // //             _head = new Node();
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         void Head_Init()
// // //         {
// // //             _head = new Node();
// // //             _head->_prev = _head;
// // //             _head->_next = _head;
// // //         }

// // //         //迭代器区间构造
// // //         template<class InputIterator>
// // //         List(InputIterator first, InputIterator last)
// // //         {
// // //             Head_Init();

// // //             while(first != last)
// // //             {
// // //                 push_back(*first);
// // //                 first++;
// // //             }
// // //         }

// // //         void swap(List<T>& lt)
// // //         {
// // //             std::swap(_head, lt._head);
// // //         }

// // //         List(const List<T>& lt)
// // //         {
// // //             Head_Init();

// // //             List<T> tmp(lt.begin(), lt.end());
// // //             swap(tmp);
// // //         }

// // //         List<T>& operator=(List<T> lt)
// // //         {
// // //             swap(lt);
// // //             return *this;
// // //         }

// // //         iterator begin()
// // //         {
// // //             return iterator(_head->_next);
// // //         }

// // //         iterator end()
// // //         {
// // //             return iterator(_head);
// // //         }

// // //         const_iterator begin()const
// // //         {
// // //             return const_iterator(_head->_next);
// // //         }

// // //         const_iterator end()const
// // //         {
// // //             return const_iterator(_head);
// // //         }

// // //         iterator insert(iterator pos, const T& x)
// // //         {
// // //             Node* cur = pos._node;
// // //             Node* newnode = new Node(x);
// // //             Node* prev = cur->_prev;

// // //             //prev newnode cur
// // //             newnode->_prev = prev;
// // //             prev->_next = newnode;
// // //             newnode->_next = cur;
// // //             cur->_prev = newnode;

// // //             return iterator(newnode);
// // //         }

// // //         iterator erase(iterator pos)
// // //         {
// // //             assert(pos != end());

// // //             Node* cur = pos._node;
// // //             Node* prev = cur->_prev;
// // //             Node* next = cur->_next;

// // //             //prev cur next
// // //             prev->_next = next;
// // //             next->_prev = prev;
// // //             delete cur;
// // //             cur = nullptr;

// // //             return iterator(next);
// // //         }

// // //         void push_back(const T& x)
// // //         {
// // //             insert(end(), x);
// // //         }

// // //         void push_front(const T& x)
// // //         {
// // //             insert(begin(), x);
// // //         }

// // //         void pop_back()
// // //         {
// // //             erase(--end());
// // //         }

// // //         void pop_front()
// // //         {
// // //             erase(begin());
// // //         }

// // //         void display()const
// // //         {
// // //             const_iterator it = begin();
// // //             while(it != end())
// // //             {
// // //                 cout << *it << " ";
// // //                 it++;
// // //             }
// // //             cout << endl;
// // //         }
// // //     private:
// // //         Node* _head;
// // //     };
// // // }

// // // int main()
// // // {
// // //     sl::List<int> lt;
// // //     lt.push_back(1);
// // //     lt.push_back(2);
// // //     lt.push_back(3);
// // //     lt.push_back(4);

// // //     lt.display();

// // //     return 0;
// // // }

// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& val = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(val)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器
// //     template<class T, class Ref, class Ptr>
// //     struct __List_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         Node* _node;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &(_node->_data);
// //             //return &(operator*());
// //         }

// //         //前置++
// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         //后置++
// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         //前置--
// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         //后置--
// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         List(const List<T>& lt)
// //         {
// //             Head_Init();

// //             List<T> tmp(lt.begin(), lt.end());
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         const_iterator begin()const
// //         {
// //             return const_iterator(_head->_next);
// //         }

// //         const_iterator end()const
// //         {
// //             return const_iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* newnode = new Node(x);
// //             Node* prev = cur->_prev;

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         iterator erase(iterator pos)
// //         {
// //             assert(pos != end());

// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* next = cur->_next;

// //             //prev cur next
// //             prev->_next = next;
// //             next->_prev = prev;
// //             delete cur;
// //             cur = nullptr;

// //             return iterator(next);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //         void push_front(const T& x)
// //         {
// //             insert(begin(), x);
// //         }

// //         void pop_back()
// //         {
// //             erase(--end());
// //         }

// //         void pop_front()
// //         {
// //             erase(begin());
// //         }

// //         void display()
// //         {
// //             iterator it = begin();
// //             while(it != end())
// //             {
// //                 cout << *it << " ";
// //                 it++;
// //             }
// //             cout << endl;
// //         }
// //     private:
// //         Node* _head;
// //     };
// // }

// // int main()
// // {
// //     sl::List<int> lt;
// //     lt.push_front(1);
// //     lt.push_front(2);
// //     lt.push_front(3);
// //     lt.push_front(4);

// //     lt.display();
// //     return 0;
// // }

// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& val = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(val)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template<class T, class Ref, class Ptr>
// //     struct __list_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         Node* _node;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &(_node->data);
// //             //return &(operator*());
// //         }

// //         //前置++
// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         //后置++
// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         //前置--
// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         //后置--
// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }

// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         const_iterator begin()const
// //         {
// //             return iterator(_head->_next);
// //         }

// //         const_iterator end()const
// //         {
// //             return iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* newnode = new Node(x);
// //             Node* prev = cur->_prev;

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {

// //         }

// //         List(const List<T>& lt)
// //         {
// //             Head_Init();

// //             List<T> tmp(lt.begin(), lt.end());
// //         }

// //     private:
// //         Node* _head;
// //     };
// // }

// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& x = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(x)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template<class T, class Ref, class Ptr>
// //     struct __list_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Node* _node;

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &_node->_data;
// //             //return &(operator*());
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }

// //         //前置++
// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         //后置++
// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         //前置--
// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         //后置--
// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         //迭代器区间构造
// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         void swap(List<T>& lt)
// //         {
// //             std::swap(_head, lt._head);
// //         }

// //         List(const List<T>& lt)
// //         {
// //             Head_Init();

// //             List<T> tmp(lt.begin(), lt.end());
// //             swap(tmp);
// //         }

// //         List<T>& operator=(List<T> lt)
// //         {
// //             swap(lt);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         const_iterator begin()const
// //         {
// //             return iterator(_head->_next);
// //         }

// //         const_iterator end()const
// //         {
// //             return iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* newnode = new Node(x);

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         iterator erase(iterator pos)
// //         {
// //             assert(pos != end());

// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* next = cur->_next;

// //             //prev cur next
// //             prev->_next = next;
// //             next->_prev = prev;
// //             delete cur;
// //             cur = nullptr;

// //             return iterator(next);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //         void push_front(const T& x)
// //         {
// //             insert(begin(), x);
// //         }

// //         void pop_back()
// //         {
// //             erase(--end());
// //         }

// //         void pop_front()
// //         {
// //             erase(begin());
// //         }

// //         void display()
// //         {
// //             iterator it = begin();
// //             while(it != end())
// //             {
// //                 cout << *it << " ";
// //                 it++;
// //             }
// //             cout << endl;
// //         }

// //     private:
// //         Node* _head;
// //     };
// // }

// // int main()
// // {
// //     sl::List<int> lt;
// //     lt.push_back(1);
// //     lt.push_back(2);
// //     lt.push_back(3);
// //     lt.push_back(4);

// //     lt.display();

// //     return 0;
// // }

// // namespace sl
// // {
// //     //节点类
// //     template <class T>
// //     struct list_node
// //     {
// //         list_node(const T &x = T())
// //             : _prev(nullptr), _next(nullptr), _data(x)
// //         {
// //         }

// //         list_node<T> *_prev;
// //         list_node<T> *_next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template <class T, class Ref, class Ptr>
// //     struct __list_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Node* _node;

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &(operator*());
// //             //return &_node->_data;
// //         }

// //         //前置++
// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         //后置++
// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         //前置--
// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         //后置--
// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         //迭代器区间构造
// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         void swap(List<T>& lt)
// //         {
// //             std::swap(_head, lt._head);
// //         }

// //         List(const List<T>& lt)
// //         {
// //             Head_Init();

// //             List<T> tmp(lt.begin(), lt.end());
// //             swap(tmp);
// //         }

// //         List<T>& operator=(List<T> lt)
// //         {
// //             swap(lt);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         const_iterator begin()const
// //         {
// //             return iterator(_head->_next);
// //         }

// //         const_iterator end()const
// //         {
// //             return iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* newnode = new Node(x);

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev =newnode;

// //             return iterator(newnode);
// //         }

// //         iterator erase(iterator pos)
// //         {
// //             assert(pos != end());

// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* next = cur->_next;

// //             //prev cur next
// //             prev->_next = next;
// //             next->_prev = prev;
// //             delete cur;
// //             cur = nullptr;

// //             return iterator(next);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //         void push_front(const T& x)
// //         {
// //             insert(begin(), x);
// //         }

// //         void pop_back()
// //         {
// //             erase(--end());
// //         }

// //         void pop_front()
// //         {
// //             erase(begin());
// //         }

// //         void display()
// //         {
// //             iterator it = begin();
// //             while(it != end())
// //             {
// //                 printf("%d ", *it);
// //                 it++;
// //             }

// //             printf("\n");
// //         }
// //     private:
// //         Node* _head;
// //     };
// // }


// // int main()
// // {
// //     sl::List<int> lt;
// //     lt.push_back(1);
// //     lt.push_back(2);
// //     lt.push_back(3);
// //     lt.push_back(4);

// //     lt.display();

// //     return 0;
// // }


// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& val = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(val)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template<class T, class Ref, class Ptr>
// //     struct __list_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Node* _node;

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &_node->_data;
// //             //return &(operator*());
// //         }

// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         Self& operator--()
// //         {
// //             _node = _node->_perv;
// //             return *this;
// //         }

// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         //迭代器区间构造
// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         void swap(List<T>& lt)
// //         {
// //             std::swap(_head, lt._head);
// //         }

// //         //拷贝构造
// //         //List<T> t2(t1);
// //         List(const List<T>& lt)
// //         {
// //             Head_Init();

// //             List<T> tmp(lt.begin(), lt.end());
// //             swap(tmp);
// //         }

// //         //赋值重载
// //         //t1 = t2;
// //         List<T>& operator=(List<T> lt)
// //         {
// //             swap(lt);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         const_iterator begin()const
// //         {
// //             return const_iterator(_head->_next);
// //         }

// //         const_iterator end()const
// //         {
// //             return const_iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* newnode = new Node(x);

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //         void display()
// //         {
// //             iterator lt = begin();
// //             while(lt != end())
// //             {
// //                 cout << *lt << " ";
// //                 lt++;
// //             }
// //             cout << endl;
// //         }

// //     private:
// //         Node* _head;

// //     };
// // }


// // int main()
// // {
// //     sl::List<int> lt;
// //     lt.push_back(1);
// //     lt.push_back(2);
// //     lt.push_back(3);
// //     lt.push_back(4);
// //     lt.display();

// //     return 0;
// // }

// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& x = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(x)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template<class T, class Ref, class Ptr>
// //     struct __List_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Node* _node;

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &_node->_data;
// //             //return &(operator*());
// //         }

// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         //迭代器区间构造
// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         void swap(List<T>& lt)
// //         {
// //             std::swap(_head, lt._head);
// //         }

// //         List(const List<T>& lt)
// //         {
// //             List<T> tmp(lt.begin(), lt.end());
// //             swap(tmp);
// //         }

// //         List<T>& operator=(List<T> lt)
// //         {
// //             swap(lt);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         const_iterator begin()const
// //         {
// //             return const_iterator(_head->_next);
// //         }

// //         const_iterator end()const
// //         {
// //             return const_iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* newnode = new Node(x);
// //             Node* prev = cur->_prev;

// //             //prev newnode cur
// //             newnode->_prev = prev;
// //             perv->_next = newnode;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //     private:
// //         Node* _head;
// //     };
// // }


// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& val = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(val)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template<class T, class Ref, class Ptr> 
// //     struct __list_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         Node* _node;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         } 

// //         Ptr operator->()
// //         {
// //             return &_node->_data;
// //             //return &(operator*());
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }

// //         //前置++
// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         //后置++
// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         //前置--
// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         //后置--
// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         //迭代器区间构造
// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void swap(List<T>& lt)
// //         {
// //             std::swap(_head, lt._head);
// //         }

// //         List(const List<T>& lt)
// //         {
// //             Head_Init();

// //             List<T> tmp(lt.begin(), lt.end());
// //             swap(tmp);
// //         }

// //         List<T>& operator=(List<T> lt)
// //         {
// //             swap(lt);
// //             return *this;
// //         }

// //         iterator begin()
// //         {
// //             return iterator(_head->_next);
// //         }

// //         iterator end()
// //         {
// //             return iterator(_head);
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* prev = cur->_prev;
// //             Node* newnode = new Node(x);

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //         void display()
// //         {
// //             iterator it = begin();
// //             while(it != end())
// //             {
// //                 cout << *it << " ";
// //                 it++;
// //             }
// //             cout << endl;
// //         }



// //     private:
// //         Node* _head;
// //     };
// // }


// // int main()
// // {
// //     sl::List<int> lt;
// //     lt.push_back(1);
// //     lt.push_back(2);
// //     lt.push_back(3);
// //     lt.push_back(4);
// //     lt.display();

// //     return 0;
// // }



// // namespace sl
// // {
// //     //节点类
// //     template<class T>
// //     struct list_node
// //     {
// //         list_node(const T& x = T())
// //             :_prev(nullptr)
// //             ,_next(nullptr)
// //             ,_data(x)
// //         {}

// //         list_node<T>* _prev;
// //         list_node<T>* _next;
// //         T _data;
// //     };

// //     //迭代器类
// //     template<class T, class Ref, class Ptr>
// //     struct __list_iterator
// //     {
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, Ref, Ptr> Self;

// //         __list_iterator(Node* node)
// //             :_node(node)
// //         {}

// //         Node* _node;

// //         Ref operator*()
// //         {
// //             return _node->_data;
// //         }

// //         Ptr operator->()
// //         {
// //             return &_node->_data;
// //             //return &operator*();
// //         }

// //         bool operator==(const Self& lt)
// //         {
// //             return _node == lt._node;
// //         }

// //         bool operator!=(const Self& lt)
// //         {
// //             return _node != lt._node;
// //         }

// //         //前置++
// //         Self& operator++()
// //         {
// //             _node = _node->_next;
// //             return *this;
// //         }

// //         //后置++
// //         Self operator++(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_next;
// //             return tmp;
// //         }

// //         //前置--
// //         Self& operator--()
// //         {
// //             _node = _node->_prev;
// //             return *this;
// //         }

// //         //后置--
// //         Self operator--(int)
// //         {
// //             Self tmp(*this);
// //             _node = _node->_prev;
// //             return tmp;
// //         }
// //     };

// //     //List类
// //     template<class T>
// //     class List
// //     {
// //     public:
// //         typedef list_node<T> Node;
// //         typedef __list_iterator<T, T&, T*> iterator;
// //         typedef __list_iterator<T, const T&, const T*> const_iterator;

// //         List()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         void Head_Init()
// //         {
// //             _head = new Node();
// //             _head->_prev = _head;
// //             _head->_next = _head;
// //         }

// //         template<class InputIterator>
// //         List(InputIterator first, InputIterator last)
// //         {
// //             Head_Init();

// //             while(first != last)
// //             {
// //                 push_back(*first);
// //                 first++;
// //             }
// //         }

// //         iterator insert(iterator pos, const T& x)
// //         {
// //             Node* cur = pos._node;
// //             Node* newnode = new Node(x);
// //             Node* prev = cur->_prev;

// //             //prev newnode cur
// //             prev->_next = newnode;
// //             newnode->_prev = prev;
// //             newnode->_next = cur;
// //             cur->_prev = newnode;

// //             return iterator(newnode);
// //         }

// //         void push_back(const T& x)
// //         {
// //             insert(end(), x);
// //         }

// //     private:
// //         Node* _head;

// //     };
// // }


// namespace sl
// {
//     //节点类
//     template<class T>
//     struct list_node
//     {
//         list_node(const T& x = T())
//             :_prev(nullptr)
//             ,_next(nullptr)
//             ,_data(x)
//         {}

//         list_node<T>* _prev;
//         list_node<T>* _next;
//         T _data;
//     };

//     //迭代器类
//     template<class T, class Ref, class Ptr>
//     struct __list_iterator
//     {
//         typedef list_node<T> Node;

//         typedef __list_iterator<T, Ref, Ptr> Self;

//         __list_iterator(Node* node)
//             :_node(node)
//         {}

//         Node* _node;

//         Ref operator*()
//         {
//             return _node->_data;
//         }

//         Ptr operator->()
//         {
//             return &_node->_data;
//         }

//         Self& operator++()
//         {
//             _node = _node->_next;
//             return *this;
//         }

//         Self operator++(int)
//         {
//             Self tmp(*this);
//             _node = _node->_next;
//             return tmp;
//         }

//         Self& operator--()
//         {
//             _node = _node->_prev;
//             return *this;
//         }

//         Self operator--(int)
//         {
//             Self tmp(*this);
//             _node = _node->_prev;
//             return tmp;
//         }

//         bool operator==(const Self& lt)
//         {
//             return _node == lt._node;
//         }

//         bool operator!=(const Self& lt)
//         {
//             return _node != lt._node;
//         }
//     };

//     //List类
//     template<class T, class Ref, class Ptr>
//     class List
//     {
//     public:
//         typedef list_node<T> Node;
//         typedef __list_iterator<T, T&, T*> iterator;
//         typedef __list_iterator<T, const T&, const T*> const_iterator;

//         List()
//         {
//             _head = new Node();
//             _head->_prev = _head;
//             _head->_next = _head;
//         }

//         template<class InputIterator>
//         List(InputIterator first, InputIterator last)
//         {

//         }

//         void push_back(const T& x)
//         {
            
//         }

//     private:
//         Node* _head;
//     };
// }


// #include<iostream>
// using std::cout;
// using std::endl;


// int main()
// {
//     cout << "Hello World" << endl;

//     return 0;
// }



ce sl
{
    // 节点类
    template<class T>
    struct _list_node
    {
        typedef _list_node<T> node;
        
        T _val;
        node* _prev;
        node* _next;

        _list_node(const T& val = T())
            : _val(val)
            , _prev(nullptr)
            , _next(nullptr)
        {}
    };

    // 迭代器类
    template<class T, class Ref, class Ptr>
    struct _list_iterator 
    {
        typedef _list_node<T> node;
        typedef _list_iterator<T, Ref, Ptr> self;

        node* _node;

        _list_iterator(node* pnode)
            : _node(pnode)
        {}

        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        bool operator==(const self& lt) const
        {
            return _node == lt._node;
        }

        bool operator!=(const self& lt) const
        {
            return _node != lt._node;
        }

        Ref operator*()
        {
            return _node->_val;
        }

        Ptr operator->()
        {
            return &_node->_val;
        }
    };

    // List类
    template<class T>
    class List
    {
    public:
        typedef _list_node<T> node;
        typedef _list_iterator<T, T&, T*> iterator;
        typedef _list_iterator<const T, const T&, const T*> const_iterator;

        node* _head;

        List()
        {
            _head = new node();
            _head->_prev = _head;
            _head->_next = _head;
        }

        void head_init()
        {
            _head = new node();
            _head->_prev = _head;
            _head->_next = _head;
        }

        template<class InputIterator>
        List(InputIterator first, InputIterator last)
        {
            head_init();

            while(first != last)
            {
                push_back(*first);
                first++;
            }
        }

        void swap(List<T>& lt)
        {
            std::swap(_head, lt._head);
        }

        List(const List<T>& lt)
        {
            head_init();

            List<T> tmp(lt.begn(), lt.end());
            swap(tmp);
        }

        List<T>& operator=(List<T> lt)
        {
            swap(lt);
            return *this;
        }

        ~List()
        {
            clear();

            delete _head;
            _head = nullptr;
        }

        // 迭代相关函数
        iterator begin()
        {
            return iterator(_head->_next);
        }

        iterator end()
        {
            return iterator(_head);
        }

        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }

        const_iterator end() const
        {
            return const_iterator(_head);
        }

        // 容器操作函数
        void clear()
        {
            iterator it = begin();

            while(it != end())
            {
                it = erase(it);
            }
        }

        T& front()
        {
            return *begin();
        }

        T& back()
        {
            return *(--end());
        }

        const T& front() const
        {
            return *begin();
        }

        const T& back() const
        {
            return *(--end());
        }

        // 随机插入 / 删除函数
        void insert(iterator pos, const T& val)
        {
            assert(pos->_node);

            node* newnode = new node(val);

            node* cur = pos->_node;
            node* prev = cur->_prev;

            newnode->_next = cur;
            cur->_prev = newnode;

            newnode->_prev = prev;
            prev->_next = newnode;
        }

        iterator erase(iterator pos)
        {
            assert(pos->_node);
            assert(pos != end());

            node* cur = pos->_node;
            node* prev = cur->_prev;
            node* next = cur->_next;

            delete cur;

            prev->_next = next;
            next->_prev = prev;

            return iterator(next);
        }

        void push_back(const T& val)
        {
            insert(end(), val);
        }


    };
}



